1. Field of the Invention
The present invention relates to Random Access Memory (RAM) based first-in, first-out (FIFO) memories. More specifically, the present invention relates to methods and apparatus for detecting a half-full condition of the FIFO memories by employing a row pointer design which generates addresses for reordering the row filling sequence of an array.
While the present invention is described herein with reference to illustrative embodiments for particular applications, it should be understood that the invention is not limited thereto. Those having ordinary skill in the art and access to the teachings provided herein will recognize additional modifications, applications, and embodiments within the scope thereof and additional fields in which the present invention would be of significant utility.
2. Description of the Related Art
A Random Access Memory (RAM) is regularly employed as a data storage device in computer systems. A FIFO memory is a buffer device designed to temporarily store data generated at a high rate of speed by a first component until a second slower component can accept and use the data. The FIFO memory can be a two-dimensional array with data stored at a predetermined memory location as specified by row and column addresses. The entry of new data displaces the original stored data by shifting the original data to another memory address. Thereafter, data exits the FIFO memory at a time commensurate with the availability of the second component.
Customarily, these devices are equipped with circuitry that detects and indicates their full or empty condition. When the empty condition occurs, it is no longer possible to read data out of the FIFO memory. When the full condition is achieved, on the other hand, it is no longer possible to write data into the FIFO memory. Often, the user has little control over the incoming and outgoing data stream and adequate warning is necessary before the reading-out or writing-in process must be stopped. Therefore, in addition to detecting the empty and full conditions of the FIFO memory, it is also necessary to detect the half-full condition to provide the user with adequate notice prior to achieving the empty or full condition. Notice is typically provided by status flags implemented electronically which tend to appear without warning.
Several methods are known in the art to provide notice of an impending memory full condition. A first approach involved the utilization of two counters as an adjunct to the FIFO memory which served to count the words entering and exiting the memory. The write word count was then compared with the read word count to indicate the empty, full or half-full condition of the memory.
A significant shortcoming with this first approach has been that as the depth of the FIFO memory has increased, the size of the counter has become increasingly large. This has slowed the operation of the counter and, consequently, that of the FIFO memory. The increased activity of larger counters also resulted in increased line loading on the counter register further slowing the counting process. The problem was further exacerbated by the increase in size of the FIFO memory since status flags became increasingly important with larger memory size.
A second approach to detect the remaining capacity of a FIFO memory involved a monitoring of the read and write row and column pointers. The empty and full conditions were detected when the read row pointer and the write row pointer each pointed to the same row and when the read column pointer and the write column pointer each pointed to the same column. This was a simple and inexpensive method to implement status flags for indicating the remaining capacity of the FIFO memory.
However, with this second approach, the half-full FIFO memory condition was not easily detected. The detection of the half-full condition while utilizing the normal sequential row filling order has been difficult because the write row pointer was pointing to a row that was "N/2" rows ahead of the read row pointer where "N" is the total number of rows in the FIFO memory. Although the logic was simple (write row N and read row N/2), the fact that the rows "N" and "N/2" were physically separated by half of the memory array required that a wire be routed from row "N" to row "N/2" where a logical AND gate was located. This scheme was expensive in terms of chip area as it required the routing of "N/2" lines (128 lines in certain prior art schemes) between the leads of the write row and read row pointers. The routing of these additional "N/2" lines potentially occupied about 25% of the surface area of the die substrate, which was prohibitive.
Also, because of the physical separation of the rows "N" and "N/2" line loading on the "N/2" lines was increased since the FIFO memory must be traversed in both the horizontal and vertical directions. Therefore, detection of the half-full condition in a FIFO memory was also slower using this second approach.
Thus, there is a need in the art for a memory counting scheme for deeper and faster FIFO memories having a design which permits the write row pointer to point to a row which is adjacent to the row pointed to by the read row pointer during the half-full condition. This design eliminates the counters positioned as an adjunct to the memory, minimizes both the area of the die substrate and line loading and does not delay the operation of the FIFO memory.